package com.arron.algorithm.leetcodetop100.贪心;

import com.arron.algorithm.leetcodetop100.动态规划.无重叠区间_动态规划;

import java.util.Arrays;

/**
 *  动态规划解法 详见
 *  @see 无重叠区间_动态规划
 */
public class 无重叠区间_贪心 {



    public int eraseOverlapIntervals(int[][] intervals) {


        int n = intervals.length;

        //按照区间右端点排序 ,,,
        //[1,11],[2,12],[11,22],[1,100]
        Arrays.sort(intervals, (a,b)->a[1]-b[1]);

        int right = intervals[0][1];
        int count = 1;

        for (int i = 1; i < n; i++) {

            if (intervals[i][0] >= right){
                count++;
                right =intervals[i][1];
            }


        }

        return n-count;
    }






    public static void main(String[] args) {

        无重叠区间_贪心 objk = new 无重叠区间_贪心();

        int[][] arrays = {{1,2},{1,2},{1,2}};
        System.out.println(objk.eraseOverlapIntervals(arrays));

    }
    //[-73,-26],[-65,-11],[-63,2],[-62,-49],[-52,31],[-40,-26],[-31,49],[30,47],[58,95],[66,98],[82,97],[95,99]

}



